Military operations require up-to-date information as to the location and intent of each object in a potential battlespace. Objects are located by various forms of sensors. A simple example of a sensor might be a soldier stationed near the battlespace, using his eyes, possibly with the aid of binoculars, and reporting object location by wireless. Another useful type of sensor is the radar system, which has the advantage of being able to survey a space from afar. The collection and use of this information to locate and discern the intent of an object is known as “Command and Control.” The intent may be expressed as the object being “hostile,” “neutral,” or “friendly.”
Information relating to a battlespace may come from many different sensors, and any one object in a battlespace may be observed by multiple sensors. Due to unavoidable limitations on the accuracy of sensor observations, there is the potential for confusion between and among the various sensors, so that sophisticated “fusion” techniques are used to fuse the data from the sensors, so as to resolve ambiguities as to what is actually sensed.
One technique for discerning the intent of an object is to associate the intent with the location or source of the object. As an example, an object sensed to be airborne over hostile territory, or tracked as having originated from a location in hostile territory, may be deemed to be hostile in the absence of countervailing information.
Given that an object is identified by a sensor as existing in the potential battlespace, it is desirable to be able to quickly identify its location relative to any particular type of territory. A preexisting system associates the various land masses of the Earth, and more particularly the various political subdivisions, into regions defined by polygons. FIG. 1 is a simplified representation of a peninsula land mass 10 including a coastline 12. Coastline 12 appears smooth at the resolution of FIG. 1, but is actually rough. The portion of coastline 12 within circle 14 contains bays, inlets, and other features, which are followed, at the resolution of the polygon, as illustrated by detailed coastline portion 14′. Depending upon the size of the political subdivision 14, it may be represented by a single polygon or, as in FIG. 1, by a plurality of juxtaposed polygons A, B, C, and D. Polygon A is defined by vertices A1, A2, A3, A4, and innumerable other vertices associated with its coastline. Similarly, polygon B is defined by vertices B1, B2, B3, B4, and other vertices associated with its coastline. Vertex A2 of polygon A is the same as, or contiguous with, vertex B1 of polygon B. For completeness, polygon C is defined by vertices C1, C2, C3, and C4, and other vertices associated with its coastline, and polygon D is defined by vertices D1, D2, D3, and D4, and other vertices associated with its coastline. Each vertex is defined by its latitude and longitude.
One function of a Command and Control system is analysis to determine, from the sensed (and possibly fused) location information relating to each object, whether it lies within one of the polygons of political subdivision 14. This type of problem is typically solved by a computer algorithm. One method for solution is termed a “Crossing Number” (CN) method, and another method is the “Winding Number” (WN). In the CN method, the number of times a ray originating at the target crosses the polygon boundary edges is noted, and the target is deemed to be outside the polygon when the crossing number is even, and inside when it is odd. The CN and WN methods are conceptually similar; however the arithmetics of the implementations differ. In the WN method, the number of times the polygon winds around or about the target is noted, and the target is deemed to be outside the polygon when the number equals zero, and within otherwise. The winding number method starts at a vertex of the polygon and steps through each segment of the polygon comparing the target point to the segment, keeping a running count of whether the target point is to the left or to the right of the line segment, thus decrementing the running count if the target point is to the right, and incrementing the running count if to the left. If, after traversing all the line segments, the running total is not zero, the point is within the polygon. In a version of the winding number method, the right/left check is only performed on those segments where the range or domain of the segment overlaps the corresponding coordinate of the point. This version of the winding number algorithm, while more computationally efficient than the basic algorithm, is still of complexity O(n), where n is the number of line segments.
The complexity of the winding number method as applied to polygons having many line segments requires computation times which make it less desirable for use in a Command and Control system, as the location information may arrive after the usefulness of the information is past. The number of segments associated with a coastline is very large.
A more rapid method of determining whether the point is within the polygon is desired.